
Khan S. Alam 3 https://E-next.in
A minimum spanning tree is a spanning tree in which the total weight of the edges are
guaranteed to be minimum of all possible paths in graph.
A spanning tree is a tree that contains all the vertices in the graph.
While creating a spanning tree, following properties must be considered:-
o Every vertex is included.
o The total edge weight of spanning tree is the minimum possible weight that
includes a path between any 2 vertices.
The overall cost of a network is minimized.
2) The Shortest Path through a network :-
If we are required to find shortest path between two nodes of a network (eg : say
between 2 cities in an airline) , then we have to use the “shortest path algorithm”.
The shortest path algorithm was first proposed by Dijkstra.
Dijkstra’s algorithm gives the shortest path between any two nodes in a network.
It can be used for finding costs of the shortest paths between 2 adjacent vertices.
This algorithm is often used in routing as a subroutine in other graph algorithms , or in
GPS Technology. Also it is widely used in network routing protocols (mostly in OSPF) to
find shortest route between two places.
11.6 Write algorithms to (university):
d) insertArc
algorithm insertArc (val graph <graphHead pointer>.
val fromKey <keyType>,
val toKey <keyType>)
Adds an arc between two vertices.
Pre graph is a pointer to a graph head structure
fromKey is the key of the originating vertex
toKey is the key of the destination vertex
Post Arc added to adjacency list
Return +1 if successful
-1 is memory overflow
-2 if fromKey not found
-3 if toKey not found
1 if (memory full)
return -1
Locate source vertex
2 fromPtr = graph->first
3 loop (fromPtr not null AND fromKey > fromPtr->data.key)
1 fromPtr =fromPtr->nextVertex
4 if (fromPtr null OR fromKey not equal fromPtr->data.key)
1 return -2
Now locate to vertex
5 toPtr = graph->first
6 loop (toPtr not null AND toKey > toPtr->data.key)
1 toPtr = toPtr->nextVertex
7 if (toPtr null OR toKey not equal toPtr ->data.key)
1 return -3
From and to vertices located. Insert new arc
8 fromPtr->outDegree = fromPtr->outDegree + 1
9 toPtr->inDegree = toPtr->inDegree + 1
10 allocate (newPtr)
First find source and destination vertex
Change indegree and outdegree
Allocate new and assign its dest
n
to
dest
n
PTR
If sorce arc null insert first
Find location
PRE and LOCN
If pre null insert before first arc
Else assign it after PRE
NEW->NEXT = LOCN